package com.company.ljh.medium;
/**
 * 77.给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 你可以按 任何顺序 返回答案。
 *
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/5/31 17:50
 * @version:1.0
 */
public class 组合 {
    /**
     * 递归，然后当list满足长度时添加到结果并停止递归
     * 注意递归时要从i+1开始
     */
    public List<List<Integer>> combine(int n, int k) {
        List <List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        digui(result,temp,k,1,n);
        return result;
    }
    private void digui(List<List<Integer>> result, List<Integer> temp,int k,int start,int n){
        for(int i = start;i<=n;i++){
            if(!temp.contains(i)){
                List<Integer> newList = new ArrayList<Integer>();
                newList.addAll(temp);
                newList.add(i);
                if(k !=1){
                    digui(result,newList,k-1,i+1,n);
                }else{
                    result.add(newList);
                }
            }
        }
    }
}
